package bucket_sort

import (
	//"log"
	"algorithm/src/quick_sort"
)

//BucketSort 桶排序
//主要思想是把待排序的数据均匀地分组，
//分组函数与桶的数据是关键
//分组后对每组使用某一种排序算法
func BucketSort(nums []int) []int {
	ln := len(nums)
	if ln < 2 {
		return nums
	}
	buckets := buildBuckets(nums)

	nNums := []int{}
	for _, bucket := range buckets {
		num := quick_sort.QuickSort(bucket)
		nNums = append(nNums, num ...)
	}
	return nNums
}

func buildBuckets(nums []int) [][]int {
	min := getMinElement(nums)
	max := getMaxElement(nums)

	gap := (max-min) / 10

	buckets := make([][]int, 10)
	for _, v := range nums {
		i := (v - min )/gap
		if i > 9  { i = 9 }
		buckets[i] = append(buckets[i], v)
	}
	return buckets
}

func getMinElement(nums []int) int {
	min := nums[0];
	for _, v := range nums {
		if min > v {
			min = v
		}
	}
	return min
}

func getMaxElement(nums []int) int {
	max := nums[0]
	for _, v := range nums {
		if max < v {
			max = v
		}
	}
	return max
}